# -*- coding: utf-8 -*-

import time


def fib(n):  # 递归算法
    if n < 2:
        return 1
    else:
        return fib(n - 1) + fib(n - 2)


def fib1(n):  # 递推算法
    if n < 2:
        return 1
    else:
        f1 = f2 = 1
        for k in range(1, n):
            f1, f2 = f2, f2 + f1
        return f2

n = 40

start = time.time()
ret = fib(n)
end = time.time()
print("Result = " + str(ret))
print("Calculation time = " + str(end - start) + "Second")

start = time.time()
ret = fib1(n)
end = time.time()
print("Result = " + str(ret))
print("Calculation time = " + str(end - start) + "Second")
